Online-Academy
Look, Read, Understand, Apply

Operating System

Memory Management

  1. What is the main purpose of Memory Management in an OS?

    Answer: The primary purposes are:

    • Allocation: To keep track of which parts of memory are currently being used and by whom.
    • Deallocation: To free memory when a process releases it.
    • Protection: To ensure that one process cannot access the memory space of another process.
    • Relocation: To allow multiple processes to reside in memory simultaneously and execute safely, even if they are loaded at different physical addresses.
    • Swapping: To move processes between main memory and disk to maximize the number of processes in the system.

  2. What is the difference between Logical (Virtual) Address and Physical Address?

    Answer:

    • Logical/Virtual Address: An address generated by the CPU during program execution. It is a reference to a memory location from the program's perspective (e.g., address 100).
    • Physical Address: An address that actually exists in the hardware's main memory (RAM) (e.g., address 12345).
    • Translation: The Memory Management Unit (MMU) hardware translates logical addresses to physical addresses at runtime. This allows processes to have a consistent, 0-based address space, regardless of where they are physically loaded in RAM.

  3. What is the difference between Internal Fragmentation and External Fragmentation?

    Answer:

    • Internal Fragmentation: Wasted space inside an allocated block of memory. Occurs when memory is allocated in fixed-size partitions (e.g., paging). If a process requests 18KB but is given a 20KB page/frame, the remaining 2KB is unused and wasted.
    • External Fragmentation: Wasted space between allocated blocks of memory. Occurs in variable-partition allocation (e.g., dynamic partitioning). As processes load and exit, small gaps (holes) of free memory are scattered throughout. Even if the total free memory is large enough to load a process, the holes are not contiguous, so the memory cannot be used.

  4. Explain Fixed Partitioning (Static Partitioning).

    Answer: Memory is divided into fixed-size partitions at system boot time (e.g., Partition 1: 10MB, Partition 2: 20MB, etc.).

    • Advantages: Simple to implement with very little OS overhead.
    • Disadvantages:
      • Internal fragmentation occurs if a process doesn't fit perfectly into a partition.
      • Limits the number of active processes (you cannot run more processes than partitions).
      • Inefficient if processes don't match partition sizes (a small process wastes a large partition).

  5. Explain Dynamic Partitioning (Variable Partitioning).

    Answer: Memory is divided dynamically to exactly fit the needs of processes. When a process arrives, it is allocated a block of memory exactly its size (or slightly larger with minimal internal fragmentation).

    • Advantages: No internal fragmentation, and you can have many processes until memory runs out.
    • Disadvantages:
      • Suffers from External Fragmentation. Over time, memory becomes riddled with small holes.
      • Requires compaction (shuffling memory to combine holes) to solve fragmentation, which is CPU-intensive.

  6. Name three algorithms used to allocate memory in Dynamic Partitioning and explain which one is generally the best.

    Answer:

    • First Fit: Allocate the first hole that is big enough. (Fastest).
    • Best Fit: Allocate the smallest hole that is big enough. (Leaves the smallest leftover hole, which causes the worst external fragmentation over time).
    • Worst Fit: Allocate the largest hole. (Leaves a large leftover hole, which can be useful for future large processes).
    • Best Overall: First Fit is generally considered the best in terms of speed and efficiency. It is fast and, in simulations, performs as well or better than Best Fit.

  7. Explain the concept of Paging.

    Answer: Paging divides both the physical memory and the logical memory into fixed-size blocks.

    • Physical memory is divided into Frames (e.g., 4KB each).
    • Logical memory is divided into Pages (same size as frames).
    • A Page Table is maintained per process to map a logical page number to a physical frame number.
    • Key Point: Since frames are fixed size, paging eliminates external fragmentation. However, it suffers from internal fragmentation (the last page of a process may not be completely full).

  8. How does the CPU translate a Logical Address to a Physical Address in a Paging system?

    Answer: The logical address is split into two parts by the MMU:

    1. Page Number (p): Used as an index into the process's Page Table to find the Frame Number (f).
    2. Page Offset (d): The exact location inside the page/frame. The offset does not change during translation.
    3. The Physical Address is calculated as: (Frame Number × Frame Size) + Offset.

  9. What is a Translation Look-aside Buffer (TLB)?

    Answer: The TLB is a small, extremely fast, hardware cache inside the MMU. It stores recently used page-table entries (Page Number -> Frame Number mappings).

    • How it works: When the CPU needs to translate an address, it first checks the TLB. If the mapping is found (a TLB hit), translation happens in one clock cycle. If not (a TLB miss), the OS must search the page table in main memory (which is slow). The TLB drastically improves the performance of paging.

  10. Explain Segmentation. How does it differ from Paging?

    Answer: Segmentation divides a process's logical memory into variable-sized segments based on the program's logical structure (e.g., Code segment, Data segment, Stack segment). Each segment has a name and a length.

    • Implementation: Each logical address is a pair <segment-number, offset>.
    • The OS maintains a Segment Table mapping the segment number to a physical base address and a limit (length).
      • Difference from Paging:
    - Paging is invisible to the programmer (hardware view); Segmentation is visible to the programmer (user view).
    - Paging uses fixed sizes; Segmentation uses variable sizes.
    - Paging has internal fragmentation; Segmentation has external fragmentation (because segments are variable sizes).

  11. What is Virtual Memory?

    Answer: Virtual Memory is a technique that separates the user's logical memory from physical memory. It allows a program to execute even if it is only partially loaded into main memory. This creates the illusion of having more physical RAM than actually exists. 

    Benefits:
    - Programs are no longer limited by physical memory size.
    - Allows more processes to run simultaneously because only active parts are loaded.
    - Enables easier sharing of libraries and code.

  12. What is Demand Paging?

    Answer: Demand paging is a popular implementation of virtual memory. Pages are only loaded into physical memory when they are actually needed (i.e., when the CPU tries to access a page that is not yet loaded). This prevents loading unused code/data at program startup, reducing I/O time and memory usage.

  13. What happens when a program tries to access a page that is not currently in physical memory (a Page Fault)?

    Answer:

    1. The MMU triggers a page fault trap, and the OS takes control.
    2. The OS checks if the memory reference is valid (is it a legitimate part of the process?).
    3. If valid, the OS finds a free frame in physical memory.
    4. It schedules a disk I/O operation to read the required page from the swap space/disk into the free frame.
    5. While I/O occurs, the CPU is given to another process (context switch).
    6. When I/O completes, the OS updates the page table to show the page is now in memory.
    7. The OS returns control to the process, which restarts the instruction that caused the page fault.

  14. What is the difference between Swapping and Demand Paging?

    Answer:

    • Swapping: The entire process is moved (swapped) in and out of main memory to the disk. It is a whole-process relocation.
    • Demand Paging: Only individual pages of a process are moved between memory and disk, as they are needed. It is much more efficient because it doesn't require moving the entire process image.

  15. What is the concept of Thrashing?

    Answer: Thrashing occurs when a process spends more time paging (handling page faults) than executing. This happens when the system does not have enough physical frames to hold the active working set of all running processes. The CPU becomes extremely busy servicing page faults, disk I/O skyrockets, and CPU utilization drops dramatically. The system effectively halts.

  16. Explain the following Page Replacement Algorithms: FIFO, LRU, and Optimal.

    Answer:

    • FIFO (First-In, First-Out): Replaces the page that has been in memory the longest. Simple to implement via a queue. However, suffers from Belady's Anomaly (adding more frames can increase page faults).
    • LRU (Least Recently Used): Replaces the page that has not been used for the longest period of time. Based on the principle of locality. Excellent performance but difficult to implement perfectly (requires hardware support).
    • Optimal (OPT): Replaces the page that will not be used for the longest period of time in the future. Achieves the lowest possible page fault rate. However, it is impossible to implement in practice because it requires knowing the future. It is used as a benchmark to compare other algorithms.

  17. Given a reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Calculate the number of page faults using FIFO and LRU with 3 frames.

    Answer: 

    - FIFO (3 frames):
    - 1: [1] Fault (1)
    - 2: [1,2] Fault (2)
    - 3: [1,2,3] Fault (3)
    - 4: [2,3,4] Fault (4) (Replaces 1)
    - 1: [3,4,1] Fault (5) (Replaces 2)
    - 2: [4,1,2] Fault (6) (Replaces 3)
    - 5: [1,2,5] Fault (7) (Replaces 4)
    - 1: [1,2,5] Hit
    - 2: [1,2,5] Hit
    - 3: [2,5,3] Fault (8) (Replaces 1)
    - 4: [5,3,4] Fault (9) (Replaces 2)
    - 5: [5,3,4] Hit
    - Total Faults: 9

- LRU (3 frames):
    - 1: [1] Fault (1)
    - 2: [1,2] Fault (2)
    - 3: [1,2,3] Fault (3)
    - 4: [2,3,4] Fault (4) (Replaces 1)
    - 1: [3,4,1] Fault (5) (Replaces 2)
    - 2: [4,1,2] Fault (6) (Replaces 3)
    - 5: [1,2,5] Fault (7) (Replaces 4)
    - 1: [1,2,5] Hit
    - 2: [1,2,5] Hit
    - 3: [2,5,3] Fault (8) (Replaces 1 - Least recent)
    - 4: [5,3,4] Fault (9) (Replaces 2)
    - 5: [5,3,4] Hit
    - Total Faults: 9
    (Note: In this specific string, both yield 9. Usually, LRU performs better than FIFO, but not always.)

  18. What is the difference between a global and a local page replacement strategy?

    Answer:

    • Local Replacement: When a process experiences a page fault, it can only replace one of its own allocated frames. The set of frames for each process is fixed. This provides isolation (one process cannot steal frames from another).
    • Global Replacement: When a process experiences a page fault, it can replace any frame in the entire system, including frames belonging to other processes. This is more flexible and usually leads to better overall system throughput (since OS can allocate frames based on demand), but a bad process can accidentally harm others.

  19. Explain the concept of Working Set and why it is important for page replacement.

    Answer: The Working Set of a process is the set of pages that the process is currently using (actively referenced) in a specific time interval.

    Importance: The OS can use the working set model to determine how many frames a process needs to run without thrashing. If the working set size is greater than the number of allocated frames, thrashing occurs. The OS should maintain the system by ensuring that the total working set sizes of all processes do not exceed the total available physical frames.

  20. A system uses paging. The page size is 4KB. A logical address is 32 bits. How many bits are used for the Page Number and how many for the Offset? What is the maximum number of pages a process can have?

    Answer: 

    - Page Size = 4KB = 2 power 12 bytes.
- Therefore, the Offset requires 12 bits.
- Logical Address is 32 bits total.
- Therefore, the Page Number uses 32 - 12 = 20 bits.
- Maximum number of pages a process can have = 2 power 20 = 1,048,576 pages (approx. 1 million).